package Demo24;

/**
 * 点名
 * https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
 * 我们可以发现一个规律,如果没有少,那mid的值 和mid(下标是相等的) 那就 left = mid + 1  去右边的找
 * 如果 mid 的值  不等于 mid 下标 那就去 left 和 mid 之间找 不能是 mid - 1 如果是就会有可能跳过
 *
 * 最后处理边界问题 假设数组是 0 1 2 3 4  最后left/right 的值是 4,和 值相等 , 那这种情况是没有少值的,我们就得返回 left + 1
 */

class Solution {
    public int takeAttendance(int[] records) {
        int left = 0,right = records.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        if(records[left] == left) return left + 1;
        return left; 
    }
}